﻿namespace Algorithms_DataStruct_Lib;

public class Sorting
{
    /// <summary>
    /// 冒泡排序
    /// </summary>
    /// <param name="array"></param>
    public static void BubbleSort(int[] array)
    {
        for (int partIndex = array.Length - 1; partIndex > 0; partIndex--)
        {
            for (int i = 0; i < partIndex; i++)
            {
                if (array[i] > array[i + 1])
                {
                    Swap(array, i, i + 1);
                }
            }
        }
    }

    /// <summary>
    ///  选择排序
    /// </summary>
    /// <param name="array"></param>
    public static void SelectionSort(int[] array)
    {
        int n = array.Length;
        for (int partIndex = n - 1; partIndex > 0; partIndex--)
        {
            int largestAt = 0;
            for (int i = 1; i <= partIndex; i++)
            {
                if (array[i] > array[largestAt])
                {
                    largestAt = i;
                }
            }

            Swap(array, largestAt, partIndex);
        }
    }

    /// <summary>
    /// 插入排序
    /// </summary>
    /// <param name="array"></param>
    public static void InsertionSort(int[] array)
    {
        int n = array.Length;
        for (int partIndex = 1; partIndex < n; partIndex++)
        {
            int curUnsorted = array[partIndex];
            int i = 0;
            for (i = partIndex; i > 0 && array[i - 1] > curUnsorted; i--)
            {
                array[i] = array[i - 1];
            }

            array[i] = curUnsorted;
        }
    }

    /// <summary>
    /// 希尔排序
    /// </summary>
    /// <param name="array"></param>
    public static void ShellSort(int[] array)
    {
        int n = array.Length;
        int gap = 1;
        while (gap < n / 3)
            gap = 3 * gap + 1;
        while (gap >= 1)
        {
            for (int i = gap; i < n; i++)
            {
                for (int j = i; j >= gap && array[j] < array[j - gap]; j -= gap)
                {
                    Swap(array, j, j - gap);
                }
            }

            gap /= 3;
        }
    }

    /// <summary>
    /// 合并排序
    /// </summary>
    /// <param name="array"></param>
    public static void MergeSort(int[] array)
    {
        int n = array.Length;
        int[] aux = new int [n];
        Sort(0, n - 1);

        void Sort(int low, int high)
        {
            if (high <= low)
            {
                return;
            }

            int mid = (high + low) / 2;
            Sort(low, mid);
            Sort(mid + 1, high);
            Merge(low, mid, high);
        }

        void Merge(int low, int mid, int high)
        {
            if (array[mid] <= array[mid + 1])
                return;
            int i = low;
            int j = mid + 1;
            Array.Copy(array, low, aux, low, high - low + 1);
            for (int k = low; k <= high; k++)
            {
                if (i > mid)
                    array[k] = aux[j++];
                else if (j > high)
                    array[k] = aux[i++];
                else if (aux[j] < aux[i])
                    array[k] = aux[j++];
                else
                {
                    array[k] = array[i++];
                }
            }
        }
    }

    /// <summary>
    /// 快速排序
    /// </summary>
    /// <param name="array"></param>
    public static void QuickSort(int[] array)
    {
        int n = array.Length;
        Sort(0, n - 1);

        void Sort(int low, int high)
        {
            if (high <= low)
                return;
            int j = Partition(low, high);
            Sort(low, j - 1);
            Sort(j + 1, high);
        }

        int Partition(int low, int high)
        {
            int i = low;
            int j = high + 1;

            int pivot = array[low];
            while (true)
            {
                while (array[++i] < pivot)
                {
                    if (i == high)
                        break;
                }

                while (pivot < array[--j])
                {
                    if (j == low)
                        break;
                }

                if (i >= j)
                    break;
                Swap(array, i, j);
            }

            Swap(array, low, j);
            return j;
        }
    }

    private static void Swap(int[] array, int i, int j)
    {
        if (i == j)
            return;
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}